package com.lw.leetcode.linked.c;

/**
 * Created with IntelliJ IDEA.
 * 1206. 设计跳表
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/4 11:50
 */
public class Skiplist {

    public static void main(String[] args) {
        Skiplist test = new Skiplist();


        int[] arr = {1, 39, 34, 13, 33, 11, 19, 38, 17, 26, 7, 21, 38, 27, 24, 24, 11, 31, 25, 13};

//        int length = 20;
//        int[] arr = Utils.getArr(length >> 1, 0, length);

//        for (int i : arr) {
//            System.out.print(i + "  ");
//            test.add(i);
//            Node tt = test.root;
//            while (tt != null) {
//                System.out.println(tt);
//                tt = tt.down;
//            }
//            System.out.println();
//        }
//        Arrays.sort(arr);
//        System.out.println(Arrays.toString(arr));


        test.add(2);
        System.out.println(test.search(3));
        System.out.println(test.search(4));
        test.add(4);
        System.out.println(test.search(4));
        test.add(5);
        System.out.println(test.search(3));
        System.out.println(test.search(5));
        System.out.println(test.erase(5));
        System.out.println(test.search(5));
        System.out.println(test.erase(2));
        System.out.println(test.erase(2));
        System.out.println(test.erase(3));
        System.out.println(test.erase(4));
        System.out.println(test.erase(5));

        Node tt = test.root;
        while (tt != null) {
            System.out.println(tt);
            tt = tt.down;
        }
        System.out.println();
    }

    private Node root = new Node(Integer.MIN_VALUE);

    public Skiplist() {

    }

    public boolean search(int target) {
        Node node = find(root, target);
        return node.next != null && node.next.val == target;
    }

    public void add(int num) {
        Node node = find(root, num);
        Node item = add(node, num, null);
        while (getFlag()) {
            Node up = getUp(node);
            if (up == null) {
                Node a = new Node(Integer.MIN_VALUE);
                Node b = new Node(num);
                a.next = b;
                b.pre = a;
                a.down = root;
                root.up = a;
                b.down = item;
                item.up = b;
                root = a;
                return;
            }
            node = up.up;
            item = add(node, num, item);
        }
    }

    public boolean erase(int num) {
        Node node = find(root, num);
        if (node.next == null || node.next.val != num) {
            return false;
        }
        Node item = node.next;
        Node next = item.next;
        node.next = next;
        if (next != null) {
            next.pre = node;
        }
        while (item.up != null || getFlag()) {
            Node up = getUp(item);
            if (up == null) {
                if (root.next == null && root.down != null) {
                    root = root.down;
                    root.up = null;
                    item.down.up = null;
                }
                return true;
            }
            up = up.up;
            if (up.val == Integer.MIN_VALUE) {
                return true;
            }
            item = del(up);
        }
        return true;
    }

    private Node del(Node item) {
        Node next = item.next;
        Node node = item.pre;
        node.next = next;
        if (next != null) {
            next.pre = node;
        }
        item.down.up = null;
        return item;
    }

    private Node add(Node node, int num, Node node2) {
        Node item = new Node(num);
        node = getPre(node, num);
        Node next = node.next;
        node.next = item;
        item.pre = node;
        if (next != null) {
            item.next = next;
            next.pre = item;
        }
        if (node2 != null) {
            node2.up = item;
            item.down = node2;
        }
        return item;
    }

    private Node getPre(Node node, int num) {
        while (node.next != null && node.next.val < num) {
            node = node.next;
        }
        return node;
    }

    private Node getUp(Node node) {
        while (node != null && node.up == null) {
            node = node.pre;
        }
        return node;
    }

    private Node find(Node node, int target) {
        while (node.next != null && node.next.val < target) {
            node = node.next;
        }
        if (node.down == null) {
            return node;
        }
        return find(node.down, target);
    }

    private boolean getFlag() {
        return Math.random() < 0.5D;
    }

    private static class Node {
        private int val;
        private Node pre;
        private Node next;
        private Node up;
        private Node down;

        public Node(int val) {
            this.val = val;
        }
    }

}
